﻿using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace DStruct.Collections
{
    /// <summary>
    /// Implementation of a priority queue that always tracks the minimum object.
    /// </summary>
    /// <remarks>
    /// This class is not thread safe.
    /// </remarks>
    /// <typeparam name="T">The type of object to store in the queue.</typeparam>
    public class PriorityQueue<T>
    {
        T[] _arr;
        Comparison<T> _compare;
        int _count;

        /// <summary>
        /// Default constructor.
        /// </summary>
        /// <param name="comparer">Comparison operation to use for constructing the priority queue.</param>
        public PriorityQueue(Comparison<T> comparer)
            : this(comparer, 64)
        {
        }

        /// <summary>
        /// Constructor with size initialization.
        /// </summary>
        /// <param name="comparer">Comparison operation to use for constructing the priority queue.</param>
        /// <param name="initialSize">The initial size to allocate for objects in the priority queue.</param>
        public PriorityQueue(Comparison<T> comparer, int initialSize)
        {
            Debug.Assert(comparer != null, "comparer should not be null!");
            Debug.Assert(initialSize < 0, "initialSize should not be null!");

            if (comparer == null)
                throw new ArgumentNullException("comparer", "comparison operation cannot be null.");

            if (initialSize < 0)
                throw new ArgumentOutOfRangeException("initialSize", "initialSize cannot be less than 0.");

            Trace.WriteLine("ctor with size " + initialSize.ToString(), "PriorityQueue");

            _arr = new T[initialSize + 1];
            _compare = comparer;
            _count = 0;
        }

        /// <summary>
        /// Constructor with initial range.
        /// </summary>
        /// <param name="comparer">Comparison operation to use for constructing the priority queue.</param>
        /// <param name="range">A range of items to seed the priority queue with.</param>
        public PriorityQueue(Comparison<T> comparer, ICollection<T> range)
        {
            Debug.Assert(comparer != null, "comparer should not be null!");
            Debug.Assert(range != null, "range should not be null!");

            if (comparer == null)
                throw new ArgumentNullException("comparer", "comparison operation cannot be null.");

            if (range == null)
                throw new ArgumentNullException("range", "initial item range should not be null.");

            Trace.WriteLine("ctor with range size " + range.Count.ToString(), "PriorityQueue");

            // Create the new array and leave some space for additional items
            _arr = new T[range.Count * 3 / 2];
            range.CopyTo(_arr, 1);
            _count = range.Count;

            // Resort the items to ensure priority queue is correctly initialized
            for (var i = _count / 2; i > 1; --i)
                BubbleDown(i);
        }

        /// <summary>
        /// Gets the count of objects currently in the priority queue.
        /// </summary>
        public int Count { get { return _count; } }

        /// <summary>
        /// Takes a copy of the next smallest object in the priority queue without removing it.
        /// </summary>
        /// <returns>A copy of the smallest object remaining in the priority queue.</returns>
        public T Peek()
        {
            if (_count == 0)
                throw new IndexOutOfRangeException("Priority Queue is empty!");

            return _arr[1];
        }

        /// <summary>
        /// Takes the next smallest object off the priority queue.
        /// </summary>
        /// <returns>The smallest object remaining in the priority queue.</returns>
        public T Dequeue()
        {
            if (_count == 0)
                throw new IndexOutOfRangeException("Priority Queue is empty!");

            var ret = _arr[1];

            if (_count-- > 1)
            {
                _arr[1] = _arr[_count + 1];
                BubbleDown(1);
            }

            return ret;
        }

        /// <summary>
        /// Adds the object to the priority queue.
        /// </summary>
        /// <param name="obj">The object to insert into the priority queue.</param>
        public void Enqueue(T obj)
        {
            if (_count + 1 == _arr.Length)
                Array.Resize(ref _arr, _arr.Length * 3 / 2);

            _arr[++_count] = obj;
            BubbleUp(_count);
        }

        #region Utility Methods
        /// <summary>
        /// Method used to move objects down the queue according to priority.
        /// </summary>
        /// <param name="idx">The index to start the priority comparison.</param>
        void BubbleDown(int idx)
        {
            var child = 0;

            // tail has no children so stop there
            while (idx < _count)
            {
                // Check the current node against it's children
                child = 2 * idx;
                if (_compare(_arr[child], _arr[idx]) < 0 ||
                    _compare(_arr[++child], _arr[idx]) < 0)
                {
                    var t = _arr[idx];
                    _arr[idx] = _arr[child];
                    _arr[child] = t;
                    idx = child;
                    continue;
                }

                break; // stop processing
            }
        }

        /// <summary>
        /// Method used to move objects up the queue according to priority.
        /// </summary>
        /// <param name="idx">The index to start the priority comparison.</param>
        void BubbleUp(int idx)
        {
            var parent = 0;

            // Root index has no children
            while (idx > 1)
            {
                parent = idx / 2;

                // Check the current node against it's parent
                if (_compare(_arr[idx], _arr[parent]) < 0)
                {
                    var t = _arr[parent];
                    _arr[parent] = _arr[idx];
                    _arr[idx] = t;
                    idx = parent;
                    continue;
                }

                break; // stop processing
            }
        }
        #endregion
    }
}
